#include "graph.h"
#include <deque>
#include <vector>

constexpr int N = 200 + 5;

std::deque<int> totalPath;
int res[N];

void resetColor() {
   for (int i = totalPath.size(); i; --i) {
      Move(totalPath.front(), 3);

      totalPath.emplace_back(totalPath.front());
      totalPath.pop_front();
   }
}

void bfs() {
   static int tmpColor = 1;

   tmpColor = 3 - tmpColor;

   std::vector<std::vector<int> > pathOfCurNode;
   pathOfCurNode.emplace_back(std::vector<int>());

   for (int curLen = 1; !pathOfCurNode.empty(); ++curLen) {
      std::vector<std::vector<int> > expandPath;

      for (auto &v : pathOfCurNode) {
         std::vector<int> backPath;

         for (int i : v)
            Move(i, tmpColor), backPath.emplace_back(LastRoad());

         int curOutDeg = NumberOfRoads();

         for (int i = 1; i <= curOutDeg; ++i) {
            Move(i, tmpColor);

            if (Color() ^ tmpColor) {
               ++res[curLen];

               expandPath.emplace_back(v);
               expandPath.back().emplace_back(i);
            }

            Move(LastRoad(), tmpColor);
         }

         if (backPath.empty())
            continue;
         for (int i = backPath.size() - 1; ~i; --i)
            Move(backPath[i], tmpColor);
      }

      std::swap(pathOfCurNode, expandPath);
   }

   resetColor();
}

void dfs() {
   int fatherRoad = LastRoad();

   bfs();

   int curOutDeg = NumberOfRoads();

   for (int i = 1; i <= curOutDeg; ++i) {
      Move(i, 3);

      int nextColor = Color();
      if (nextColor == 3)
         Move(LastRoad(), 3);
      else {
         int curRoadId = LastRoad();
         totalPath.emplace_front(curRoadId);
         totalPath.emplace_back(i);

         dfs();

         totalPath.emplace_front(i);
         totalPath.emplace_back(curRoadId);
      }
   }

   if (~fatherRoad)
      Move(fatherRoad, 3);
}

void Inspect(int R) {
   dfs();

   for (int i = 1; i <= R; ++i)
      Answer(i, res[i] >> 1);
}
